package NO3_LinkedList;

/**
 * 2025-6-27
 * 力扣 - 160.相交链表
 * <p>
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 * 思路：
 * 假设A长度为a，B长度为b，相交部分长度为c。
 * pA走完A（a步）后从B头部继续走，pB走完B（b步）后从A头部继续走。
 * 最终，pA走了a + (b - c)步，pB走了b + (a - c)步，此时它们会同时到达相交点（因为a + b - c = b + a - c）。
 * 实例：
 * 链表A：1 -> 2 -> 3 -> 4
 * 链表B：9 -> 3 -> 4
 * 相交点为节点3。
 * pA：1 → 2 → 3 → 4 → 切换到B → 9 → 3
 * pB：9 → 3 → 4 → 切换到A → 1 → 2 → 3
 */
public class GetIntersectionNodeMain {
    public static void main(String[] args) {
        // 创建公共部分
        ListNode common = new ListNode(8, new ListNode(4, new ListNode(5)));
        ListNode headA = new ListNode(4, new ListNode(1, common));
        ListNode headB = new ListNode(5, new ListNode(6, new ListNode(1, common)));

        ListNode.printNode(getIntersectionNode(headA, headB));
//        ListNode.printList(getIntersectionNode(headA, headB));
    }

    // 不会
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null){
            return null;
        }

        ListNode pA = headA;
        ListNode pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next; // 沿着A走，走到头为null后换一条路走
            pB = pB == null ? headA : pB.next; // 沿着B走
        }

        return pA;
    }
}
